package pers.qianyu.month_202102.date_20210214;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 99. 恢复二叉搜索树
 * https://leetcode-cn.com/problems/recover-binary-search-tree/
 *
 * @author mizzle rain
 * @date 2021-02-14 15:44
 */
public class RecoverTree {
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        Deque<TreeNode> st = new ArrayDeque<>();
        // 通过中序遍历，找到逆序的两个结点，分别记为 first 和 second，然后交换这两个结点
        TreeNode p = root, pre = null, first = null, second = null;
        while (p != null || !st.isEmpty()) {
            while (p != null) {
                st.addLast(p);
                p = p.left;
            }
            TreeNode node = st.pollLast();
            if (pre != null && pre.val > node.val) {
                if (first == null) {
                    first = pre;
                    second = node;
                } else {
                    second = node;
                }
            }
            pre = node;
            if (node.right != null) p = node.right;
        }
        swap(first, second);
    }

    private void swap(TreeNode left, TreeNode right) {
        int temp = left.val;
        left.val = right.val;
        right.val = temp;
    }
}
